package LearnAlgorithm.i_递归进阶andDFSand剪枝and回溯;

/*
有个小孩正在上楼梯，楼梯有n阶台阶，小孩1次可以上1阶、2阶、3阶。
请实现一个方法，计算小孩有多少种上楼的方式
为了防止溢出，请将结果mod 1000000007

给定一个正整数int n，请返回一个数，代表上楼的方式数。
n保证 <= 100000

 */
public class a走楼梯也称青蛙跳by迭代 {
	public static void main(String[] args) {
		long time1 = System.currentTimeMillis();
		System.out.println(recursion1(30));
		util.Util.duration(time1);
		long time2 = System.currentTimeMillis();
		System.out.println(recursion2(30));
		util.Util.duration(time2);
		
	}
	
	/**
	 * 递归形式
	 * O(3^N)
	 * @param n
	 * @return
	 */
	public static long recursion1(int n) {
		if (n < 0) {
			System.out.println("特殊情况。视为没有上楼梯的方式");
			return 0;
		}
		if (n == 0) {
			System.out.println("特殊情况。视为1种上楼梯方式");
			return 1;
		}
		if (n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}
		if (n == 3) {
			return 4;
		}
		return recursion1(n - 1) % 1000000007 + recursion1(n - 2) % 1000000007 + recursion1(n - 3) % 1000000007;
	}
	
	/**
	 * 迭代形式
	 * O(N)
	 * @param n
	 * @return
	 */
	public static long recursion2(int n) {
		if (n < 0) {
			System.out.println("特殊情况。视为没有上楼梯的方式");
			return 0;
		}
		if (n == 0) {
			System.out.println("特殊情况。视为1种上楼梯方式");
			return 1;
		}
		if (n == 1) {
			return 1;
		}
		if (n == 2) {
			return 2;
		}
		if (n == 3) {
			return 4;
		}
		int x1 = 1;
		int x2 = 2;
		int x3 = 4;
		for (int i = 4; i <= n; i++) {
			int x_1 = x1;
			x1 = x2;
			x2 = x3;
			x3 = ((x1 + x2) % 1000000007 + x_1) % 1000000007;//两次取余为了防止数据过大
		}
		return x3;//x3永远是第i个数的数值；
	}
}
